/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.easy._121;

/**
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.easy._121
 * @ClassName: BestTimeBuy
 * @Author: linyaonan
 * @Date: 2019/11/5 16:16
 */
public class BestTimeBuy {

    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int max = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                if (prices[i] < prices[j]) {
                    int sub = prices[j] - prices[i];
                    max = Math.max(max, sub);
                }
            }
        }
        return max;
    }

    public int maxPro(int[] prices) {
        if (prices == null || prices.length <= 1) {
            return 0;
        }
        int min = prices[0];
        int maxSum = 0;
        for (int i = 1; i < prices.length; i++) {
            min = Math.min(min, prices[i]);
            maxSum = Math.max(maxSum, prices[i] - min);
        }
        return maxSum;
    }

    /**
     * 思路三：
     * 1. 创建一个与原始数组长度一样的数组，用来记录当前位置之前的最小值
     * 2. 遍历原始数组当前值与最小值数组的[i-1]位置进行对比，记录最大差值
     * 3. 同时将新的最小值填入到最小值数组的[i]位置
     */

    public int max3(int[] prices) {
        if (prices == null || prices.length <= 1) {
            return 0;
        }
        int[] minLine = new int[prices.length];
        minLine[0] = prices[0];
        int max = 0;
        for (int i = 1; i < prices.length; i++) {
            max = Math.max(prices[i] - minLine[i - 1], max);
            minLine[i] = Math.min(minLine[i - 1], prices[i]);
        }

        return max;
    }

    public int maxProfit4(int[] prices) {
        // 1. 第一遍遍历获取到当前位置的最小值
        // 2. 第二遍遍历计算出当前值减去 index - 1的最大值
        int[] min = new int[prices.length];
        min[0] = prices[0];
        for (int i = 1; i < prices.length; i++) {
            min[i] = Math.min(min[i - 1], prices[i]);
        }

        int minR = 0;

        for (int i = 1; i < prices.length; i++) {
            minR = Math.max(minR, prices[i] - min[i - 1]);
        }

        return minR;

    }

}
